import java.util.Random;

import src.Array;
import src.ArrayQueue;
import src.LinkedQueue;
import src.LoopQueue;
import src.MaxHeap;
import src.Queue;
import src.UF.QuickFind;
import src.UF.UF;
import src.UF.UnionFind;
import src.UF.UnionFind2;
import src.UF.UnionFind3;

/**
 * 基准测试
 */
public class BaseTest {

    private static double testQueue(Queue<Integer> q, int opCount){
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            q.enQueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            q.deQueue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime)/ 1000000000.0;
    }
    public static void testQueue() {
        int opCount = 100000;
        Queue<Integer> arrQ = new ArrayQueue<>();
        Queue<Integer> loopQ = new LoopQueue<>();
        Queue<Integer> linkQ = new LinkedQueue<>();
        double arrQtime = testQueue(arrQ, opCount);
        double loopQtime = testQueue(loopQ, opCount);
        double linkQtime = testQueue(linkQ, opCount);
        System.out.println(String.format("ArrayQueue try %d const %f s", opCount, arrQtime));
        System.out.println(String.format("LoopQueue try %d const %f s", opCount, loopQtime));
        System.out.println(String.format("LinkedQueue try %d const %f s", opCount, linkQtime));
        /*
        ArrayQueue try 100000 const 37.900383 s
        LoopQueue try 100000 const 0.013677 s
        LinkedQueue try 100000 const 0.010290 s
         */
    }

    public static double testHeap(Integer[] testData, boolean isHeapify) {
        long startTime = System.nanoTime();
        MaxHeap<Integer> res;
        if (isHeapify) {
            res = new MaxHeap<>(testData);
        }else{
            res = new MaxHeap<>();
            for (int i = 0; i < testData.length; i++)
                res.add(testData[i]);
        }
        // 验证
        int max = res.popMax();
        while (! res.isEmpty()) {
            if (max < res.getMax()) throw new IllegalArgumentException("Err");
            max = res.popMax();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime)/ 1000000000.0;
    }
    public static Integer[] getRandomArr(int len) {
        Random rd = new Random();
        Integer[] res = new Integer[len];
        for (int i = 0; i < len; i++) {
            res[i] = rd.nextInt(Integer.MAX_VALUE);
        }
        return res;
    }
    public static void testHeap() {
        int opCount = 500000;
        Integer[] testData = getRandomArr(opCount);
        double noHeapifyTime = testHeap(testData, false);
        double isHeapifyTime = testHeap(testData, true);
        System.out.println(String.format("without Heapify try %d const %f s", opCount, noHeapifyTime));
        System.out.println(String.format("with Heapify try %d const %f s", opCount, isHeapifyTime));
    }

    public static double testUF(UF uf, int m){
        int size = uf.getSize();
        Random rd = new Random();
        long startTime = System.nanoTime();
        for (int i = 0; i < m; i++) {
            int a = rd.nextInt(size);
            int b = rd.nextInt(size);
            uf.unionElements(a, b);
        }
        for (int i = 0; i < m; i++) {
            int a = rd.nextInt(size);
            int b = rd.nextInt(size);
            uf.isConnected(a, b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void testUF() {
        int size = 100000;
        int m = 10000000;
        // UF uf1 = new QuickFind(size);
        UF uf2 = new UnionFind(size);
        UF uf3 = new UnionFind2(size);
        UF uf4 = new UnionFind3(size);
        UF uf5 = new UnionFind3(size);
        // System.out.println(String.format("Quick Find try %d const %f s", m, testUF(uf1, m))); // 性能太差
        System.out.println(String.format("Union Find size %d try %d const %f s", size, m, testUF(uf2, m)));
        System.out.println(String.format("Union Find v2 size %d try %d const %f s", size, m, testUF(uf3, m)));
        System.out.println(String.format("Union Find v3 size %d try %d const %f s", size, m, testUF(uf4, m)));
        System.out.println(String.format("Union Find v4 size %d try %d const %f s", size, m, testUF(uf5, m)));

    }
    public static void main(String[] args) {
        testQueue();
        // testHeap();
        // testUF();
    }

}